# Copyright 2007 Boris Dusek
#
# This file is part of grapy.
#
# Grapy is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, version 3 of the License.
#
# Grapy is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Grapy.  If not, see <http://www.gnu.org/licenses/>.


class DFSHooks:

    HOOK_OK = 0,
    HOOK_SKIP = 1,
    HOOK_ABORT = 2

    dep = []

    @staticmethod
    def dfs_main_begin(environ):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_main_vertices_order(environ,vertices):
        for v in vertices:
            yield v

    @staticmethod
    def dfs_main_visit_invoke_before(environ,vertex):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_main_visit_invoke_after(environ,vertex):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_main_visit_not_invoke(environ,vertex):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_main_end(environ):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_begin(environ,u):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_vertices_order(environ,vertices):
        for v in vertices:
            yield v

    @staticmethod
    def dfs_visit_tree_edge_before(environ,u,v):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_tree_edge_after(environ,u,v):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_back_edge(environ,u,v):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_forward_edge(environ,u,v):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_cross_edge(environ,u,v):
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_end(environ,u):
        return DFSHooks.HOOK_OK


class TimeTickerDFSHooks(DFSHooks):

    dep = []

    @staticmethod
    def dfs_main_begin(environ):
        environ.time = 0
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_begin(environ,u):
        environ.time += 1
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_end(environ,u):
        environ.time += 1
        return DFSHooks.HOOK_OK


class DiscoveryTimeDFSHooks(DFSHooks):

    dep = [TimeTickerDFSHooks]

    @staticmethod
    def dfs_main_begin(environ):
        environ.d = {}
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_begin(environ,u):
        environ.d[u] = environ.time
        return DFSHooks.HOOK_OK


class FinishingTimeDFSHooks(DFSHooks):

    dep = [TimeTickerDFSHooks]

    @staticmethod
    def dfs_main_begin(environ):
        environ.f = {}
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_end(environ,u):
        environ.f[u] = environ.time
        return DFSHooks.HOOK_OK


class ComponentsDFSHooks(DFSHooks):

    dep = []

    @staticmethod
    def dfs_main_begin(environ):
        environ.component = {}
        environ.current_component = 0
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_main_visit_invoke_before(environ,u):
        environ.current_component += 1
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_begin(environ,u):
        environ.component[u] = environ.current_component
        return DFSHooks.HOOK_OK


class PredecessorDFSHooks(DFSHooks):

    dep = []

    @staticmethod
    def dfs_main_begin(environ):
        environ.p = {}
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_main_visit_invoke_before(environ,u):
        environ.p[u] = None
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_tree_edge_before(environ,u,v):
        environ.p[v] = u
        return DFSHooks.HOOK_OK


class SortedDFSHooks(DFSHooks):

    dep = []

    @staticmethod
    def dfs_main_vertices_order(environ,vertices):
        return sorted(vertices)

    @staticmethod
    def dfs_visit_vertices_order(environ,vertices):
        return sorted(vertices)

class CoreDFSHooks(DFSHooks):

    dep = [DiscoveryTimeDFSHooks,FinishingTimeDFSHooks]


class DFSEnvironment:
    pass

class DFSHooksSuite:

    def __init__(self,hooks=None,core=True):
        # these need to be there, since distinction between forward and cross
        # edge relies on discovery and finishing times
        if hooks is None:
            hooks=[]
        if core:
            hooks[:0]=CoreDFSHooks.dep
        self.hooks=hooks

    def resolve_deps(self):
        from grapy.AdjListGraph import AdjListGraph
        from grapy.TopologicalSort import TopologicalSortDFSHooks
        # we will do a topological sort of the plugin dependencies, which is
        # kind of a "chicken and egg" problem

        # hooks needed to do the topological sort
        topo_hooks=[
                TimeTickerDFSHooks,
                DiscoveryTimeDFSHooks,
                TopologicalSortDFSHooks,
                ]
        topo_hooks_suite=DFSHooksSuite(topo_hooks,core=False)
        g=AdjListGraph(multi=False,directed=True)
        # interpreting hooks of this hook set as vertices in a DAG to sort
        que=self.hooks
        while que:
            u=que.pop(0)
            g.add_vertex(u)
            for v in u.dep:
                que.append(v)
                g.add_edge((v,u))
        dfs_environ=DFSEnvironment()
        g.DFS(topo_hooks_suite,dfs_environ)
        # get resulting hooks in topological order with dependencies resolved
        self.hooks=dfs_environ.topological_order

    def dfs_main_begin(self,environ):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_main_begin(environ)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_main_vertices_order(self,environ,vertices):
        _vertices = vertices
        for hook in self.hooks:
            _vertices = hook.dfs_main_vertices_order(environ,_vertices)
        return _vertices

    def dfs_main_visit_invoke_before(self,environ,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_main_visit_invoke_before(environ,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_main_visit_invoke_after(self,environ,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_main_visit_invoke_after(environ,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_main_visit_not_invoke(self,environ,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_main_visit_not_invoke(environ,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_main_end(self,environ):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_main_end(environ)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_visit_begin(self,environ,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_visit_begin(environ,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_visit_vertices_order(self,environ,vertices):
        _vertices = vertices
        for hook in self.hooks:
            _vertices = hook.dfs_visit_vertices_order(environ,_vertices)
        return _vertices

    def dfs_visit_tree_edge_before(self,environ,u,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_visit_tree_edge_before(environ,u,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_visit_tree_edge_after(self,environ,u,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_visit_tree_edge_after(environ,u,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_visit_back_edge(self,environ,u,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_visit_back_edge(environ,u,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_visit_forward_edge(self,environ,u,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_visit_forward_edge(environ,u,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_visit_cross_edge(self,environ,u,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_visit_cross_edge(environ,u,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret

    def dfs_visit_end(self,environ,v):
        ret = DFSHooks.HOOK_OK
        for hook in self.hooks:
            ret = hook.dfs_visit_end(environ,v)
            if ret != DFSHooks.HOOK_OK:
                break
        return ret
